package SortAlgorithm;

/**
 * @author gao
 * @date 2025/11/5 19:10
 */

public class InsertSort implements Sort {

    /**
     * 插入排序算法的实现
     * @param nums
     */
    @Override
    public void sort(int[] nums) {
        int n = nums.length;

        // 外层循环，从第二个元素开始，依次将每个元素插入到已排序序列中的适当位置
        for (int i = 1; i < n; i++) {
            int tmp = nums[i];  // 保存当前待插入元素的值
            int j = i - 1;      // 已排序序列的最后一个元素的索引

            // 内层循环，从已排序序列的最后一个元素开始，向前查找插入位置
            for (; j >= 0; j--) {
                // 如果当前元素大于待插入元素，则将当前元素向后移动一位
                if (nums[j] > tmp) {
                    nums[j + 1] = nums[j];
                } else {
                    break;  // 如果找到插入位置，则退出循环
                }
            }
            // 将待插入元素插入到正确位置
            nums[j + 1] = tmp;
        }
    }
}